Міністерство Освіти України
Національний університет "Львівська політехніка"
М Е Т О Д И Ч Н А В К А З І В К А
До лабораторної роботи № 5
На тему: “ Методи сортування. Шелла.”
з дисципліни
" Алгоритми і структури даних"
Для базового напрямку 6.0804 "Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2007 р.
Львів – 2007
Методичні вказівки до лабораторних робіти з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки"
Укладач: Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Ознайомлення із методами сортування. Зокрема із методом Шелла.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування Шелла. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу Шелла.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Сортування Шелла є досить цікавою модифікацією алгоритму сортування простими вставками.
Розглянемо наступний алгоритм сортування масиву а[0].. а[15].
INCLUDEPICTURE "http://algolist.manual.ru/sort/gif/11.gif" \* MERGEFORMATINET
1. Спочатку сортуємо простими вставками кожні 8 груп з 2-х елементів.
INCLUDEPICTURE "http://algolist.manual.ru/sort/gif/12.gif" \* MERGEFORMATINET
2. Потім сортуємо кожну з чотирьох груп по 4 елементи.
У нульовій групі будуть елементи 4, 12, 13, 18, в першій - 3, 5, 8, 9.
3. Далі сортуємо 2 групи по 8 елементів.
INCLUDEPICTURE "http://algolist.manual.ru/sort/gif/14.gif" \* MERGEFORMATINET
4. В кінці сортуємо вставками усі 16 елементів.
INCLUDEPICTURE "http://algolist.manual.ru/sort/gif/15.gif" \* MERGEFORMATINET
Очевидно, лише останнє сортування необхідне, щоб розташувати всі елементи по своїх місцях. Так навіщо потрібні останні ?
Hасправді вони просувають елементи максимально близько до відповідних позицій, так що в останній стадії число переміщень буде дуже маленьке. Послідовність і так майже відсортована.
Єдиною характеристикою сортування Шелла є приріст - відстань між сортованими елементами, залежно від проходу. В кінці приріст завжди рівний одиниці – мет3од завершується звичайним сортуванням вставками, але саме послідовність приростів визначає зростання ефективності.
Використаний в прикладі набір: 8, 4, 2, 1 - непоганий вибір, особливо, коли кількість елементів - ступінь двійки. Проте набагато кращий варіант запропонував Р.Седжвік. Його послідовність має вигляд
При використанні таких приростів середня кількість операцій: O(n7/6), у гіршому разі - порядку O(n4/3).
Звернемо увагу на те, що послідовність обчислюється в порядку, протилежному використовуваному: inc[0]= 1, inc[1]= 5 ... Формула дає спочатку менші числа, потім все більші і більші, тоді як відстань між сортованими елементами, навпаки, повинна зменшуватися. Тому масив приростів inc обчислюється перед запуском власне сортування до максимальної відстані між елементами, яка буде першим кроком в сортуванні Шелла. Потім його значення використовуються в зворотному порядку.
При використанні формули Седжвіка слід зупинитися на значенні inc[s-1], якщо 3*inc[s]> size.
int increment(long inc[], long size){
int p1, p2, p3, s;
p1 = p2 = p3 = 1;
s = -1;
do {
if (++s % 2) {
inc[s]= 8*p1 - 6*p2 + 1;
} else {
inc[s]= 9*p1 - 9*p3 + 1;
p2 *= 2;
p3 *= 2;
}
p1 *= 2;
} while(3*inc[s]< size);
return s > 0 ? --s : 0;
}
template<class T>
void shellSort(T a[], long size){
long inc, i, j, seq[40];
int s;
// обчислення послідовності приростів
s = increment(seq, size);
while (s >= 0) {
// сортування вставками з інкрементами inc[]
inc = seq[s--];
for (i = inc; i < size; i++) {
T temp = а[i];
for (j = i-inc; (j >= 0) && (а[j]> temp); j -= inc)
а[j+inc]= а[j];
а[j+inc]= temp;
}
}
}
Часто замість обчислення послідовності під час кожного зап...
